//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -10⁴ <= matrix[i][j], target <= 10⁴ 
// 
// Related Topics 数组 二分查找 矩阵 👍 655 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

public class _74_SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new _74_SearchA2dMatrix().new Solution();
        int[][] matrix = {{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
        int target = 13;
        System.out.println(solution.searchMatrix(matrix, target));
    }

    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int rowIndex = binarySearchFirstColumn(matrix, target);
            if (rowIndex == -1) return false;
            return binarySearchRow(matrix[rowIndex], target);
        }

        private boolean binarySearchRow(int[] row, int target) {
            int left = 0;
            int right = row.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (row[mid] == target) {
                    return true;
                } else if (row[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return false;
        }

        private int binarySearchFirstColumn(int[][] matrix, int target) {
            int left = 0;
            int right = matrix.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (matrix[mid][0] <= target) {
                    left = mid + 1;//left左边的都是小于等于的
                } else {
                    right = mid - 1;//right右边的都是大于的
                }
            }
            return right;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length;
            int n = matrix[0].length;
            if (target < matrix[0][0] || target > matrix[m - 1][n - 1]) return false;

            int left = 0;
            int right = m * n - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (matrix[mid / n][mid % n] == target) {
                    return true;
                } else if (matrix[mid / n][mid % n] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return false;
        }

//        private int[] searchMN(int m, int n, int i) {
//            int[] res = new int[2];
//            res[0] = i / n;
//            res[1] = i % n;
//            return res;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}